package com.lfg.other;

import com.alibaba.fastjson.JSON;

public class MaxScore {


    public static void main(String[] args) {
        Integer ret = maxScore(new int[]{41, 1, 3, 5});
        System.out.println("[" + JSON.toJSONString(ret) + "]");


        Integer ret2 = maxScore(new int[]{1, 2, 3});
        System.out.println("[" + JSON.toJSONString(ret2) + "]");
        // 6 15  9
    }

    public static int maxScore(int[] array) {
        int length = array.length;
        int[] sum = new int[length];
        int[][] dp = new int[length][length];
        sum[0] = array[0];
        for (int i = 1; i < array.length; i++) {
            sum[i] = sum[i - 1] + array[i];
            dp[i][i] = array[i];
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = i; j >= 0; j--) {
                if (j == i) {
                    dp[i][j] = array[i];
                } else {
                    int num = j == 0 ? sum[i] : sum[i] - sum[j - 1];
                    dp[j][i] = num - Math.min(dp[j + 1][i], dp[j][i - 1]);
                }
            }
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                System.out.print(dp[i][j] + ", ");
            }
            System.out.println(" ");
        }
        return dp[0][length - 1];
    }
}
//
// 11 16  = 4